The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


– log2(Pr(DPmax = x/256))
Key Size Max Value x = 8 10 12 14 16 18 20 22 24
128 bits 18/256   15.4 1.3 0.9 4.1 8.0 12.0      
192 bits 24/256   15.2 1.3 0.9 4.1 8.0 12.2 16.5 20.8 25.0
256 bits* 22/256   15.1 1.3 0.9 4.1 8.0. 12.2 16.7 22.0  
Table 7.1. DPmax Over All Keys

7.2.3 Exhaustive and Statistical Analysis

Given the fixed permutations q0 and q1, and the definitions for how to construct s0, s1, s2, and s3 from them, we have performed extensive testing of the characteristics of these key-dependent S-boxes. In the 128-bit key case, all testing has been performed exhaustively, which is feasible because each S-box uses only 16 bits of key material. In many cases, however, only statistical (i.e., Monte Carlo) testing has been possible for the larger key sizes. In this section, we present and discuss these results. It is our hope to complete exhaustive testing over time for the larger key sizes where feasible, but the probability distributions obtained for the statistical tests give us a fairly high degree of confidence that no surprises are in store.

Computing DPmax Over All Keys. Table 7.1 shows the DPmax distribution for the various key sizes. A detailed explanation of the format of this table will also help in understanding the other tables in this section. An asterisk (*) next to a key size in the tables discussed in this section indicates that the entries in that row are a statistical distribution using Monte Carlo sampling of key bits, not an exhaustive test. For example, in Table 7.1, only the 256-bit key row uses statistical sampling; the 128-bit and 192-bit cases involve an exhaustive test. Clearly, the maximum value from a statistical sample is not a guaranteed maximum.

Note that, for 128-bit keys, each S-box has a DPmax value no larger than 18/256. The remaining columns give the distribution of observed DPmax values. Each entry is expressed as the negative base-2 logarithm of the fraction of S-boxes with the given value (or value range), with blank entries indicating that no value in the range was found. For example, in the N = 128 case only one of every 212.0 key-dependent S-boxes has DPmax = 18/256, while over half (1 in 20.9) have DPmax = 12/256. These statistics are taken over all four S-boxes (s0, s1, s2, s3), so a total of 4 × 216 (i.e., 256K) S-boxes were evaluated for the 128-bit key case. Each Monte Carlo sampling involves at least 216 S-boxes, but in many cases the number is considerably larger.

Computing LPmax Over All Keys. Table 7.2 shows the distribution of LPmax for the various key sizes. Observe that the vast majority of Twofish S-boxes have LPmax < (88/256)2, although there is a small fraction of S-boxes with larger values. For 128-bit keys, no Twofish S-box has an LPmax value greater than (100/256)2, while the maximum value is somewhat higher for larger key sizes. Monte Carlo statistics are given for the larger two key sizes, since the computational load for computing LPmax is roughly a factor of 15 higher than for DPmax.

– log2(Pr(LPmax = (x/256)2))
Key size Max Value x = 56..63 64..71 72..79 80..87 88..95 96..103 104..111
128 bits (100/256)2   9.3 1.0 1.2 4.2 8.0 12.4  
192 bits* (104/256)2   9.3 1.0 1.2 4.2 8.2 12.2 17.0
256 bits* (108/256)2   9.4 1.0 1.2 4.2 8.1 12.5 17.4
Table 7.2. LPmax Over All Keys.

– log2(Pr(# fixed points = x))
Key Size Max Value x = 0 1 2 3 4 5 6 7 8 9 10
128 bits 8   1.4 1.4 2.4 4.1 6.0 8.2 11.1 14.1 17.0    
192 bits 10   1.4 1.4 2.4 4.0 6.0 8.4 10.9 13.8 16.8 19.8 23.4
256 bits* 10   1.4 1.4 2.4 4.0 6.0 8.4 10.9 13.7 16.8 21.0 21.0
random     1.4 1.4 2.4 4.0 6.0 8.3 10.9 13.7 16.7 19.9 23.2
Table 7.3. Number of Fixed Points Over All Keys


Previous Table of Contents Next